# -*- coding: utf-8 -*-
from structures.list import List
from structures.heap import Heap
from structures.unionfind import UnionFind
from graphs.graph import *


class ListGraph(Graph):

    def __init__(self, size=None):
        self.__vertices = HashTable(size)

    def add_vertex(self, name):
        self.__vertices[name] = List()

    def add_edge(self, src, dest, weight=None):
        adjacents = self.__vertices[src]
        exists = False

        for edge in adjacents:
            edgeDest = self.__vertices.get_key(edge[0])
            if dest == edgeDest:
                exists = True
                break

        if not exists:
            destIndex = self.__vertices.get_key_index(dest)
            edge = [destIndex, weight]
            adjacents.add(edge)

    def get_edge(self, src, dest):
        adjacents = self.__vertices[src]

        for edge in adjacents:
            edgeDest = self.__vertices.get_key(edge[0])
            if edgeDest == dest:
                return edge[1]

        return None

    def vertex_count(self):
        return self.__vertices.count()

    def edge_count(self):
        count = 0
        for name in self.__vertices.get_keys():
            adjacents = self.__vertices[name]
            count += adjacents.count()
        return count

    def get_vertex(self, index):
        return self.__vertices.get_key(index)

    def run_dijkstra(self, source, distance):
        if self.__vertices[source] is None:
            raise Exception('Source vertex does not exist!')

        # Stores the name of the previous node for the key
        previous = HashTable()
        # Stores the calculated distance so far for each node
        # from the source
        cost = HashTable()
        # Prority Queue
        heap = Heap()
        # Represents the value infinity
        infinity = float("inf")
        # Initialize all costs to infinity
        for name in self.__vertices.get_keys():
            cost[name] = infinity
        # Set the cost to source node to zero
        # and add to heap
        cost[source] = 0
        heap.insert(cost[source], source)
        # Count how many nodes have been added to S so far
        count = 0
        # While there are nodes missing
        # and the heap is not empty (this condition is added
        # in case the graph is not connected)
        while count < self.vertex_count() and not heap.empty():
            name = heap.extract_min()
            count += 1
            # Get vertex
            adjacents = self.__vertices[name]
            # Look for adjacent nodes
            for edge in adjacents:
                # Calculate new cost
                dest = self.__vertices.get_key(edge[0])
                weight = edge[1]
                newcost = cost[name] + weight
                # Update cost if it's smaller
                if newcost < cost[dest]:
                    cost[dest] = newcost
                    previous[dest] = name
                    heap.insert(newcost, dest)

        # Get all vertex that are at least distance
        # from source
        actors = List()
        for name in self.__vertices.get_keys():
            if distance <= cost[name]:
                actors.add(name)

        return actors

    def to_string(self):
        output = ''
        for name in self.__vertices.get_keys():
            adjacents = self.__vertices[name]
            output += name + ':'
            if adjacents.count() > 0:
                for edge in adjacents:
                    output += '(' + edge[0] + ', '
                    output += str(edge[1]) + ') '
            output += '\n'

        return output

    def save(self, filename):
        file = open(filename, 'w')
        for name in self.__vertices.get_keys():
            adjacents = self.__vertices[name]
            file.write(name + Graph.NAME_SEPARATOR)
            if adjacents.count() > 0:
                count = 0
                for edge in adjacents:
                    destinationIndex = edge[0]
                    weight = edge[1]
                    if count != 0:
                        file.write(Graph.ADJ_LIST_SEPARATOR)
                    file.write(str(destinationIndex) + Graph.WEIGHT_SEPARATOR)
                    file.write(str(weight))
                    count += 1
            file.write('\n')
        file.close()

    def load(self, filename):
        file = open(filename)

        for line in file:
            pair = line.split(Graph.NAME_SEPARATOR)
            name = pair[0].strip()
            list = pair[1].strip()
            self.add_vertex(name)
            edges = list.split(Graph.ADJ_LIST_SEPARATOR)
            for edge in edges:
                edge = edge.strip()
                if len(edge) > 0:
                    words = edge.split(Graph.WEIGHT_SEPARATOR)
                    index = int(words[0].strip())
                    weight = int(words[1])
                    self.__vertices[name].add([index, weight])

        file.close()
